package com.practice.niuke.new_direct_practice.class13;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
 * 给定一个字符串str，给定一个字符串类型的数组arr。
 * arr里的每一个字符串，代表一张贴纸，你可以把单个字符剪开使用，目的是拼出str
 * 来。
 * 返回需要至少多少张贴纸可以完成这个任务。
 * 例子：str= "babac"，arr = {"ba","c","abcd"}
 * 至少需要两张贴纸"ba"和"abcd"，因为使用这两张贴纸，把每一个字符单独剪开，含
 * 有2个a、2个b、1个c。
 * 是可以拼出str的。所以返回2。
 */
public class Code01_StickersToSpellWord {

    /**
     * 暴力递归函数
     *
     * @param rest 可变参数，剩下的字符所组成的串
     * @param arr  固定参数， 贴纸数组
     * @return 返回：搞定rest需要几张贴纸
     */
    public static int f(String rest, String[] arr) {
        if (rest.equals("")) {
            return 0;
        }
        int next = Integer.MAX_VALUE;
        for (String first : arr) {
            // 请把first中搞定的字符，在rest中减掉 -> nextRest
            String nextRest = subFirstCharacter(rest, first);
            next = Math.min(next, f(nextRest, arr));
        }
        return next + 1;
    }

    /**
     * 请把first中搞定的字符，在rest中减掉 -> nextRest
     *
     * @param rest  rest
     * @param first first
     * @return String
     */
    public static String subFirstCharacter(String rest, String first) {
        char[] restChars = rest.toCharArray();
        List<Character> nestRestList = new ArrayList<>();
        for (char restChar : restChars) {
            nestRestList.add(restChar);
        }
        char[] firstChars = first.toCharArray();
        for (char item : firstChars) {
            if (nestRestList.contains(item)) {
                nestRestList.remove(item);
            }
        }
        char[] nextChars = new char[nestRestList.size()];
        for (int i = 0; i < nestRestList.size(); i++) {
            nextChars[i] = nestRestList.get(i);
        }
        return String.valueOf(nextChars);
    }

    /**
     * 傻缓存解决方法（假设，所有贴纸的字符，都是小写a~z）
     * stickers的长度是n，意味着有n种贴纸
     * 将原始的贴纸结构变成字符统计结构：
     * 第0种贴纸为“abc”
     * 第1种贴纸为“bbc”
     * ......
     * =======>
     * [
     * [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
     * [0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
     * ......
     * ]
     *
     * @param stickers 贴纸数组
     * @param target   要搞定的字符串
     * @return int
     */
    public static int minStickers1(String[] stickers, String target) {
        int n = stickers.length;
        // 1. 生成贴纸数组的二维字符词频统计表
        int[][] map = new int[n][26];
        for (int i = 0; i < n; i++) {
            char[] str = stickers[i].toCharArray();
            for (char c : str) {
                map[i][c - 'a']++;
            }
        }
        // 2. 傻缓存dp表
        HashMap<String, Integer> dp = new HashMap<>();
        dp.put("", 0);
        // 3. 调用递归函数
        return process1(dp, map, target);
    }

    /**
     * 递归 + 傻缓存
     *
     * @param dp  傻缓存，如果t已经算过了，直接返回dp中的值
     * @param map 0..N每一个字符串所含字符的词频统计
     * @param t   剩余的目标
     * @return int
     */
    public static int process1(HashMap<String, Integer> dp, int[][] map, String t) {
        if (dp.containsKey(t)) {
            return dp.get(t);
        }
        int ans = Integer.MAX_VALUE;
        int n = map.length;
        // 将target转化为字符的词频统计
        // 如果target="bcdf",则tmp如下：
        // [0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
        int[] tmap = new int[26];
        char[] target = t.toCharArray();
        for (char c : target) {
            tmap[c - 'a']++;
        }

        for (int i = 0; i < n; i++) {
            if (map[i][target[0] - 'a'] == 0) {// 第i张贴纸没有target[0]这个字符
                continue;
            }
            // 第i张贴纸有target[0]这个字符
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < 26; j++) {
                if (tmap[j] > 0) { // (j+'a')这个字符是target需要的
                    for (int k = 0; k < Math.max(0, tmap[j] - map[i][j]); k++) {
                        // 搜集，没有被搞定的字符
                        sb.append((char) ('a' + j));
                    }
                }
            }
            // 没有被搞定的字符组成的新串（TODO：没看懂，尝试自己写这块的逻辑）
            String s = sb.toString();
            // 递归
            int tmp = process1(dp, map, s);
            if (tmp != -1) {
                ans = Math.min(ans, 1 + tmp);
            }
        }
        // 加入缓存
        dp.put(t, ans == Integer.MAX_VALUE ? -1 : ans);
        return dp.get(t);
    }

    /**
     * 傻缓存的第二种尝试思路（枚举每张贴纸的使用数量）
     *
     * @param stickers 贴纸数组
     * @param target   需要搞定的串
     * @return int
     */
    public static int minStickers2(String[] stickers, String target) {
        int n = stickers.length;
        int[][] map = new int[n][26];
        for (int i = 0; i < n; i++) {
            char[] str = stickers[i].toCharArray();
            for (char c : str) {
                map[i][c - 'a']++;
            }
        }
        char[] str = target.toCharArray();
        int[] tmap = new int[26];
        for (char c : str) {
            tmap[c - 'a']++;
        }
        HashMap<String, Integer> dp = new HashMap<>();
        int ans = process2(map, 0, tmap, dp);
        return ans;
    }

    /**
     * 递归 + 傻缓存 第2种尝试思路
     *
     * @param map  0..N每一个字符串所含字符的词频统计
     * @param i
     * @param tmap 将剩余的“要搞定的字符串”转化为字符的词频统计
     * @param dp   傻缓存
     * @return
     */
    public static int process2(int[][] map, int i, int[] tmap, HashMap<String, Integer> dp) {
        StringBuilder keyBuilder = new StringBuilder();
        keyBuilder.append(i + "_");
        for (int asc = 0; asc < 26; asc++) {
            if (tmap[asc] != 0) {
                keyBuilder.append((char) (asc + 'a') + "_" + tmap[asc] + "_");
            }
        }
        String key = keyBuilder.toString();
        if (dp.containsKey(key)) {
            return dp.get(key);
        }
        boolean finish = true;
        for (int asc = 0; asc < 26; asc++) {
            if (tmap[asc] != 0) {
                finish = false;
                break;
            }
        }
        if (finish) {
            dp.put(key, 0);
            return 0;
        }
        if (i == map.length) {
            dp.put(key, -1);
            return -1;
        }
        int maxZhang = 0;
        for (int asc = 0; asc < 26; asc++) {
            if (map[i][asc] != 0 && tmap[asc] != 0) {
                maxZhang = Math.max(maxZhang, (tmap[asc] / map[i][asc]) + (tmap[asc] % map[i][asc] == 0 ? 0 : 1));
            }
        }
        int[] backup = Arrays.copyOf(tmap, tmap.length);
        int min = Integer.MAX_VALUE;
        int next = process2(map, i + 1, tmap, dp);
        tmap = Arrays.copyOf(backup, backup.length);
        if (next != -1) {
            min = next;
        }
        for (int zhang = 1; zhang <= maxZhang; zhang++) {
            for (int asc = 0; asc < 26; asc++) {
                tmap[asc] = Math.max(0, tmap[asc] - (map[i][asc] * zhang));
            }
            next = process2(map, i + 1, tmap, dp);
            tmap = Arrays.copyOf(backup, backup.length);
            if (next != -1) {
                min = Math.min(min, zhang + next);
            }
        }
        int ans = min == Integer.MAX_VALUE ? -1 : min;
        dp.put(key, ans);
        return ans;
    }

}
